package se.kth.fericss.quicksort;
public class QuicksortRandomPivot implements Quicksorter {
	@Override
	public void sort(int[] v, int low, int high) {
		if(check.checkSpecial(v, low, high))
			return;
		helpSort(v, low, high);	
	}
	@Override
	public void helpSort(int[] v, int low, int high) {
		//  l is the lower index, h is the upper index
		//  of the region of array a that is to be sorted	
		int l=low, h=high, t;
		// Choose a random pivot element.
		int p=v[(int)(rnd.nextInt(h-l)+l)];
		//  partition
		while (l<=h)
		{   
			while (v[l]<p) l++; 
			while (v[h]>p) h--;
			if (l<=h)
			{
				t=v[l]; 
				v[l]=v[h];
				v[h]=t;
				l++; 
				h--;
			}
		}
		//  recursion
		if (low<h) helpSort(v, low, h);
		if (l<high) helpSort(v, l, high);
	}
	@Override
	public String getType() {
		return "Ramdom pivot element";
	}
}